DSC 40B Practice Problems

Problems tagged with "expected time"

Problem #009

Tags: expected time

What is the expected time complexity of the function below?


import random

def foo(n):
    # draw a random number uniformly from 0, 1, 2, ..., 99
    # in constant time
    x = random.randrange(100)
    for i in range(x):
        for j in range(n):
            print("Here!")
Solution

\(\Theta(n)\)

Problem #010

Tags: expected time

What is the expected time complexity of the function below?


import random

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1
    # in constant time
    x = random.randrange(n)
    if x < 100:
        for j in range(n**2):
            print(j)
Solution

\(\Theta(n)\)

Problem #032

Tags: expected time

What is the expected time complexity of the following function?


import random

def foo(n):
    for i in range(n):
        # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
        x = random.randrange(n)
        for j in range(x):
            print(j)
Solution

\(\Theta(n^2)\)

Problem #037

Tags: expected time

What is the expected time complexity of the function below?


import random

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
    x = random.randrange(n)
    if x < math.sqrt(n):
        for j in range(n):
            print(j)
Solution

\(\Theta(\sqrt n)\)

Problem #059

Tags: expected time

What is the expected time complexity of the following function? State your answer using asymptotic notation.


import random

def foo(n):
    x = random.randrange(n)

    if x < 8:
        for j in range(n**3):
            print(j)
    else:
        for j in range(n):
            print(j)
Solution

\(\Theta(n^2)\)

Problem #064

Tags: expected time

What is the expected time complexity of the function below? State your answer using asymptotic notation.

You may assume that math.sqrt and math.log take \(\Theta(1)\) time. math.log computes the natural log.


import random
import math

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
    x = random.randrange(n)

    if x < math.log(n):
        for j in range(n**2):
            print(j)
    elif x < math.sqrt(n):
        print('Ok!')
    else:
        for i in range(n):
            print(i)
Solution

\(\Theta(n \log n)\) There are three cases: Case 1) \(x < \log n\); Case 2) \(\log n \geq x < \sqrt n\); and Case 3) \(x \geq\sqrt{n}\).

The probability of Case 1 is \(\log n / n\). The time taken in case 1 is \(\Theta(n^2)\).

The probability of Case 2 is

\[\frac{\sqrt n}{n} - \frac{\log n}{n} = \Theta(\sqrt n / n) = \Theta(1/\sqrt n). \]

The time taken in this case is \(\Theta(1)\).

The probability of Case 3 is 1 minus the probability of the sum of the other two cases, which will simply be \(\Theta(1)\):

\[ 1 - \Theta((\log n) / n) - \Theta(1 / \sqrt{n}) = \Theta(1) \]

Therefore, the expected time is:

\[\begin{aligned} \frac{\log n}{n} \times \Theta(n^2) + \Theta(1/\sqrt n) \times \Theta(1) + \Theta(1) \times \Theta(n) &= \Theta(n \log n) + \Theta(1 / \sqrt n) + \Theta(n) \\ &= \Theta(n \log n) \end{aligned}\]

Problem #088

Tags: expected time

What is the expected time complexity of the function below?

You may assume that math.sqrt takes \(\Theta(1)\) time.


import random
import math

def foo(n):
    # draw a number uniformly at random from 0, 1, 2, ..., n-1 in Theta(1)
    x = random.randrange(n)

    if x < math.sqrt(n):
        for j in range(n):
            print(j)
    elif x < n//2:
        print('Ok!')
    else:
        for i in range(n**2):
            print(i)
Solution

\(\Theta(n^2)\)

Problem #089

Tags: expected time

What is the expected time complexity of the function below?


import random

def foo(n):
    # draw a random number uniformly from 0, 1, 2, ..., n-1
    # in constant time
    x = random.randrange(n)
    for i in range(x):
        for j in range(n):
            print("Here!")
Solution

\(\Theta(n^2)\)